package 力扣._1123_最深叶节点的最近公共祖先;

import 力扣.公用数据结构.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    int getdeepth(TreeNode root) {
        if (root == null)
            return 0;
        int l = getdeepth(root.left);
        int r = getdeepth(root.right);
        return Math.max(l, r) + 1;
    }

    void getmaxdeepnodes(TreeNode root, List<TreeNode> list, int deep, int goal_d) {
        if (root == null)
            return;
        if (deep == goal_d)
            list.add(root);
        getmaxdeepnodes(root.left, list, deep + 1, goal_d);
        getmaxdeepnodes(root.right, list, deep + 1, goal_d);
    }

    void dfs(TreeNode root, TreeNode[] nodes) {
        if (root == null)
            return;
        if (root.left != null)
            nodes[root.left.val] = root;
        if (root.right != null)
            nodes[root.right.val] = root;
        dfs(root.left, nodes);
        dfs(root.right, nodes);
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        //先找到深度
        int deepth = getdeepth(root);
        List<TreeNode> list = new ArrayList<>();
        getmaxdeepnodes(root, list, 1, deepth);

        TreeNode[] nodes = new TreeNode[1002];    //双亲表示法
        dfs(root, nodes);
        //因为深度相同所以向上向后次数后所指向节点一样即结束
        while (true) {
            boolean isallsame = true;
            int now = list.get(0).val;
            for (TreeNode node : list) {
                if (node.val != now) {
                    isallsame = false;
                    break;
                }
            }

            if (isallsame)
                return list.get(0);
            else {
                list.replaceAll(treeNode -> nodes[treeNode.val]);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.stringToTreeNode("[3,5,1,6,2,0,8,null,null,7,4]");
        TreeNode node1 = new Solution().lcaDeepestLeaves(node);
        System.out.println(node1.val);
    }
}
